Usenet 1993 July

home *** CD-ROM | disk | FTP | other *** search

/ Usenet 1993 July / InfoMagic USENET CD-ROM July 1993.ISO / sources / misc / volume15 / ggems / part01 next >

Wrap

Text File | 1990-10-14 | 59.6 KB | 2,052 lines

Newsgroups: comp.sources.misc X-UNIX-From: craig@weedeater.math.yale.edu subject: v15i023: Graphics Gems, Part 1/5 from: Craig Kolb <craig@weedeater.math.yale.edu> Sender: allbery@uunet.UU.NET (Brandon S. Allbery - comp.sources.misc) Posting-number: Volume 15, Issue 23 Submitted-by: Craig Kolb <craig@weedeater.math.yale.edu> Archive-name: ggems/part01 [Going on my third week of this, I'm afraid it's gotten beyond the point where I can keep up. I am therefore looking for a new moderator for this newsgroup. Send mail to comp.sources-misc-request@uunet.uu.net if you are interested. (Do NOT send mail to allbery@uunet.uu.net! I haven't read read my mail there for at least two weeks.) ++bsa] #! /bin/sh # This is a shell archive. Remove anything before this line, then unpack # it by saving it into a file and typing "sh file". To overwrite existing # files, type "sh file -c". You can also feed this as standard input via # unshar, or by typing "sh <file", e.g.. If this archive is complete, you # will see the following message at the end: # "End of archive 1 (of 5)." # Contents: 2DClip 2DClip/Makefile 2DClip/box.h 2DClip/line.h AALines # AALines/00README AALines/AALines.h AALines/AAMain.c # AALines/LongConst.h AALines/Makefile AALines/utah.h BinRec.c # CircleRect.c DigitalLine.c FastJitter.c FixedTrig.c HSLtoRGB.c # Hash3D.c HypotApprox.c MANIFEST MatrixOrtho.c PixelInteger.c # PolyScan PolyScan/Makefile README RGBTo4Bits.c RayBox.c # RayPolygon.c Sturm Sturm/Makefile Sturm/solve.h Sturm/util.c # TransBox.c ViewTrans.c # Wrapped by craig@weedeater on Fri Oct 12 15:53:11 1990 PATH=/bin:/usr/bin:/usr/ucb ; export PATH if test ! -d '2DClip' ; then echo shar: Creating directory \"'2DClip'\" mkdir '2DClip' fi if test -f '2DClip/Makefile' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'2DClip/Makefile'\" else echo shar: Extracting \"'2DClip/Makefile'\" $212 characters$ sed "s/^X//" >'2DClip/Makefile' <<'END_OF_FILE' XLIBFILE = ../gemslib.a X XCFLAGS = $(GENCFLAGS) -I.. X XOFILES = clip.o bio.o cross.o X X$(LIBFILE): $(OFILES) X ar rcs $(LIBFILE) $(OFILES) X Xclean: X /bin/rm -f clip.o bio.o cross.o X X$(OFILES): line.h ../GraphicsGems.h END_OF_FILE if test 212 -ne `wc -c <'2DClip/Makefile'`; then echo shar: \"'2DClip/Makefile'\" unpacked with wrong size! fi # end of '2DClip/Makefile' fi if test -f '2DClip/box.h' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'2DClip/box.h'\" else echo shar: Extracting \"'2DClip/box.h'\" $186 characters$ sed "s/^X//" >'2DClip/box.h' <<'END_OF_FILE' X X/* X * file box.h X * a short include file is better then no include file X */ Xtypedef struct { /* guess what this is */ X long _lowx; X long _lowy; X long _highx; X long _highy; X} BOX; X X END_OF_FILE if test 186 -ne `wc -c <'2DClip/box.h'`; then echo shar: \"'2DClip/box.h'\" unpacked with wrong size! fi # end of '2DClip/box.h' fi if test -f '2DClip/line.h' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'2DClip/line.h'\" else echo shar: Extracting \"'2DClip/line.h'\" $1795 characters$ sed "s/^X//" >'2DClip/line.h' <<'END_OF_FILE' X X/* XTwo-Dimensional Clipping: A Vector Based Approach Xby Hans Spoelder and Fons Ullings Xfrom "Graphics Gems", Academic Press, 1990 X*/ X X X/* X * file line.h X * contains major definitions for the clipping routines X * X */ X#define NFAC 10 /* discrete measure */ X X#define SCALE (1 << NFAC) /* 1024 points/cm */ X#define TO_INT(X) ((int)((X)*SCALE)) X#define TO_FLT(X) (((float)(X))/SCALE) X X#define COINCIDE 1 /* what do the lines do */ X#define PARALLEL 2 X#define CROSS 3 X#define NO_CROSS 4 X X#define STD 0 /* crossing types */ X#define DELAY 1 X X#define CLIP_NORMAL 1 X Xtypedef struct { /* holds a point */ X long _x; /* holds x coordinate */ X long _y; /* holds y coordinate */ X} POINT; X Xtypedef struct { /* holds a cross point */ X POINT _p; /* holds the solution */ X short _type; /* more information */ X} CLIST; X Xstruct segment { /* holds a segment */ X POINT _from; /* start coordinates */ X POINT _to; /* stop coordinates */ X struct segment *_next; X struct segment *_prev; X}; X X X#define SEGMENT struct segment X Xstruct contour { /* holds a contour */ X short _no; /* contour counter */ X short _status; /* holds information */ X short _cnt; /* number of elements */ X SEGMENT *_s; /* the segments */ X struct contour *_next; /* linked list */ X long _minx; /* coordinates of box */ X long _miny; X long _maxx; X long _maxy; X}; X X#define CONTOUR struct contour X X#define ACTIVE 01 /* polygon attributes */ X#define NORMAL 02 X X#define SET_ON(p) ((p)->_status |= ACTIVE) X#define SET_NORMAL(p) ((p)->_status |= NORMAL) X X#define SET_OFF(p) ((p)->_status &= ~ACTIVE) X#define SET_INVERSE(p) ((p)->_status &= ~NORMAL) X X#define IS_ON(p) ((p)->_status & ACTIVE) X#define IS_NORMAL(p) ((p)->_status & NORMAL) X Xextern CONTOUR *CL; X XCONTOUR *get_contour_ptr(); X Xextern short C_COUNT; X END_OF_FILE if test 1795 -ne `wc -c <'2DClip/line.h'`; then echo shar: \"'2DClip/line.h'\" unpacked with wrong size! fi # end of '2DClip/line.h' fi if test ! -d 'AALines' ; then echo shar: Creating directory \"'AALines'\" mkdir 'AALines' fi if test -f 'AALines/00README' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'AALines/00README'\" else echo shar: Extracting \"'AALines/00README'\" $1074 characters$ sed "s/^X//" >'AALines/00README' <<'END_OF_FILE' XThis group of files is a simple demonstration of an anti-aliased line Xrenderer from _Grahpics_Gems_. Files in the release are: X X 00README -- This information file. X X Makefile -- Makefile for creating the demo executable. X X AALines.h -- Include file for demo source files. X X AALines.c -- Rendering code from _Grahpics_Gems_ pages 690-693. X X AATables.c -- Initialization code for frame buffer and lookup tables. X X AAMain.c -- Calling routine for the renderer. X X utah.h -- Include file for friendly Utah RLE front end. X X utah.c -- Source for friendly Utah RLE front end. X XAs it is written, the program dumps its frame buffer to a Utah RLE Xfile. You need to obtain the Utah RLE library from another source; Xtry the following FTP sites: X X cs.utah.edu (128.110.4.21) X weedeater.math.yale.edu (130.132.23.17) X freebie.engin.umich.edu (35.2.68.23) X XIt should be fairly easy to dump the frame buffer to another type Xof file, or straight to a display device. See AAMain.c. X XHave fun. X X -- Kelvin Thompson, 18 August 1990 X kelvin@cs.utexas.edu END_OF_FILE if test 1074 -ne `wc -c <'AALines/00README'`; then echo shar: \"'AALines/00README'\" unpacked with wrong size! fi # end of 'AALines/00README' fi if test -f 'AALines/AALines.h' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'AALines/AALines.h'\" else echo shar: Extracting \"'AALines/AALines.h'\" $1371 characters$ sed "s/^X//" >'AALines/AALines.h' <<'END_OF_FILE' X/* FILENAME: AALines.h [revised 17 AUG 90] X X AUTHOR: Kelvin Thompson X X DESCRIPTION: Symbols and globals for the anti-aliased line X renderer. X X #INCLUDED IN: X AAMain.c -- Calling routine for renderer. X AATables.c -- Initialization routines for lookup tables. X AALines.c -- Rendering code. X*/ X X/* frame buffer to hold the anti-aliased line */ X#define xpix 60 X#define ypix 60 Xextern char *fbuff; X X/* macros to access the frame buffer */ X#define PIXADDR(xx,yy) (fbuff+(yy)*xpix+(xx)) X#define PIXINC(dx,dy) ((dy)*xpix+(dx)) X X/* fixed-point data types and macros */ Xtypedef int FX; Xtypedef unsigned int UFX; X#define FX_FRACBITS 16 /* bits of fraction in FX format */ X#define FX_0 0 /* zero in fixed-point format */ X#define FLOAT_TO_FX(flt) ((FX)((flt)*(1<<FX_FRACBITS)+0.5)) X X/* some important constants */ X#define PI 3.1415926535897932384626433832795028841971693993751 X#define SQRT_2 1.4142135623730950488016887242096980785696718753769 X X/* square-root function globals */ Xextern UFX *sqrtfunc; Xextern int sqrtcells; Xextern int sqrtshift; X#define SQRTFUNC(fxval) (sqrtfunc[ (fxval) >> sqrtshift ]) X X/* AA globals */ Xextern float line_r; /* line radius */ Xextern float pix_r; /* pixel radius */ Xextern FX *coverage; Xextern int covercells; Xextern int covershift; X#define COVERAGE(fxval) (coverage[ (fxval) >> covershift ]) END_OF_FILE if test 1371 -ne `wc -c <'AALines/AALines.h'`; then echo shar: \"'AALines/AALines.h'\" unpacked with wrong size! fi # end of 'AALines/AALines.h' fi if test -f 'AALines/AAMain.c' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'AALines/AAMain.c'\" else echo shar: Extracting \"'AALines/AAMain.c'\" $1578 characters$ sed "s/^X//" >'AALines/AAMain.c' <<'END_OF_FILE' X/* FILENAME: AAMain.c [revised 17 AUG 90] X X AUTHOR: Kelvin Thompson X X DESCRIPTION: Calling routine for anti-aliased line renderer. X This routine calls the line renderer to draw a single X anti-aliased line into a small frame buffer. The X routine then dumps the frame buffer to a Utah RLE file X 'anti.rle'. X X LINK WITH: X utah.h -- Definitions for friendly Utah RLE front end. X AALines.h -- Shared tables, symbols, etc. for renderer. X AALines.c -- Rendering code. X AATables.c -- Table initialization. X*/ X X#include <stdio.h> X#include <math.h> X#include "AALines.h" X#include "utah.h" X X X Xmain ( argc, argv ) Xint argc; Xchar *argv[]; X{ Xint i; Xchar *scanptr; Xint x1,y1,x2,y2; X X/* initialize frame buffer and look-up tables */ XAnti_Init(); X X/* set line endpoints */ Xx1 = 2; y1 = 2; Xx2 = 25; y2 = 55; X X/* render anti-aliased line to a frame buffer */ XAnti_Line( x1,y1, x2,y2 ); X X X/* The code below dumps the frame buffer to a Utah RLE file. X** It should be pretty easy to rewrite so that it dumps to X** any other kind of output file...or straight to a display X** device. The frame buffer is an array of characters X** starting at 'fbuff' with size 'xpix' by 'ypix'. */ X X { X /* thanks to A.T. Campbell for the friendly front end */ X UTAH_FILE *picout; X picout = utah_write_init( "anti.rle", xpix, ypix ); X if ( picout == NULL ) X { perror("anti.rle"); exit(1); } X for ( i=0; i<ypix; i++ ) X { X scanptr = &fbuff[i*xpix]; X utah_write_rgb( picout, scanptr, scanptr, scanptr ); X } X utah_write_close(picout); X } X} END_OF_FILE if test 1578 -ne `wc -c <'AALines/AAMain.c'`; then echo shar: \"'AALines/AAMain.c'\" unpacked with wrong size! fi # end of 'AALines/AAMain.c' fi if test -f 'AALines/LongConst.h' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'AALines/LongConst.h'\" else echo shar: Extracting \"'AALines/LongConst.h'\" $1701 characters$ sed "s/^X//" >'AALines/LongConst.h' <<'END_OF_FILE' X/* FILENAME: LongConst.h [revised 18 AUG 90] X X AUTHOR: Kelvin Thompson X X DESCRIPTION: High-precision constants. If this file is included X in the same file as GraphicsGems.h, this file must come *after* X GraphicsGems.h. (It's okay to use this file without GraphicsGems.h.) X X The standard _Graphics_Gems_ include file has some constants X that do not have full double-precision accuracy. This file X has the constants to a ridiculously high precision. See pages X 434-435 of _Graphics_Gems_. I got the constants from Mathematica. X X Also, this file has a constant and macro for finding the base-two X logarithm of a number. X*/ X X/* prevent multiple inclusion */ X#ifndef __LONGCONST_H__ X#define __LONGCONST_H__ X X/* first get rid of stuff from GraphicsGems.h */ X#undef PI X#undef PITIMES2 X#undef PIOVER2 X#undef E X#undef SQRT2 X#undef SQRT3 X#undef GOLDEN X#undef DTOR X#undef RTOD X X/* re-define basic constants with high precision */ X#define PI 3.141592653589793238462643383279502884197169399375105820975 X#define E 2.718281828459045235360287471352662497757247093699959574967 X#define SQRT2 1.414213562373095048801688724209698078569671875376948073177 X#define SQRT3 1.732050807568877293527446341505872366942805253810380628056 X#define GOLDEN 1.618033988749894848204586834365638117720309179805762862135 X X/* re-define derived constants */ X#define PITIMES2 (2.0*PI) X#define PIOVER2 (0.5*PI) X#define DTOR (PI/180.0) X#define RTOD (180.0/PI) X X/* macro and constant for base 2 logarithm */ X#define LN2 0.693147180559945309417232121458176568075500134360255254121 X#define LOG2(val) (log(val)*(1.0/LN_2)) X X#endif /* __LONGCONST_H__ */ END_OF_FILE if test 1701 -ne `wc -c <'AALines/LongConst.h'`; then echo shar: \"'AALines/LongConst.h'\" unpacked with wrong size! fi # end of 'AALines/LongConst.h' fi if test -f 'AALines/Makefile' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'AALines/Makefile'\" else echo shar: Extracting \"'AALines/Makefile'\" $462 characters$ sed "s/^X//" >'AALines/Makefile' <<'END_OF_FILE' X# FILENAME: Makefile [revised 18 AUG 90] X# X# AUTHOR: Kelvin Thompson X# X# DESCRIPTION: Makefile for anti-aliased line rendering demo. X X# locations of Utah RLE information XUTAH_RLE_INCLUDE_DIR = /public/graphics/rle/include XUTAH_RLE_LIB_FILE = /p/lib/librle.a X XCFLAGS = -I$(UTAH_RLE_INCLUDE_DIR) X XOBJS = AAMain.o AALines.o AATables.o utah.o X X%.o : %.c X $(CC) -c $(CFLAGS) $(CPPFLAGS) $< X XAALine : $(OBJS) X cc $(CFLAGS) -o $@ $(OBJS) $(UTAH_RLE_LIB_FILE) -lm END_OF_FILE if test 462 -ne `wc -c <'AALines/Makefile'`; then echo shar: \"'AALines/Makefile'\" unpacked with wrong size! fi # end of 'AALines/Makefile' fi if test -f 'AALines/utah.h' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'AALines/utah.h'\" else echo shar: Extracting \"'AALines/utah.h'\" $877 characters$ sed "s/^X//" >'AALines/utah.h' <<'END_OF_FILE' X/* X file: utah.h X description: interface to Utah RLE toolkit X author: A. T. Campbell X date: October 30, 1989 X*/ X X#ifndef UTAH_H X#define UTAH_H X X/******************************************************************************/ X X/* include files */ X#include "svfb_global.h" X X/******************************************************************************/ X X/* type definitions */ Xtypedef struct sv_globals UTAH_FILE; X X/******************************************************************************/ X X/* return values */ Xextern int utah_read_close(); Xextern UTAH_FILE *utah_read_init(); Xextern int utah_read_pixels(); Xextern int utah_read_rgb(); Xextern int utah_write_close(); Xextern UTAH_FILE *utah_write_init(); Xextern int utah_write_pixels(); Xextern int utah_write_rgb(); X X/******************************************************************************/ X X#endif UTAH_H END_OF_FILE if test 877 -ne `wc -c <'AALines/utah.h'`; then echo shar: \"'AALines/utah.h'\" unpacked with wrong size! fi # end of 'AALines/utah.h' fi if test -f 'BinRec.c' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'BinRec.c'\" else echo shar: Extracting \"'BinRec.c'\" $1171 characters$ sed "s/^X//" >'BinRec.c' <<'END_OF_FILE' X/* X * Recording Animation in Binary Order for Progressive Temporal Refinement X * by Paul Heckbert X * from "Graphics Gems", Academic Press, 1990 X */ X X/* X * binrec.c: demonstrate binary recording order X * X * Paul Heckbert Jan 90 X */ X X#include <stdio.h> X Xmain(ac, av) Xint ac; Xchar **av; X{ X int nframes, i, start_frame, repeat_count; X if (ac!=2) { X fprintf(stderr, "Usage: binrec <nframes>\n"); X exit(1); X } X nframes = atoi(av[1]); X X printf("step startframe repeatcount\n"); X for (i=0; i<nframes; i++) { X inside_out(nframes, i, &start_frame, &repeat_count); X printf(" %2d %2d %2d\n", i, start_frame, repeat_count); X } X} X X/* X * inside_out: turn a number "inside-out": a generalization of bit-reversal. X * For n = power of two, this is equivalent to bit-reversal. X * X * Turn the number a inside-out, yielding b. If 0<=a<n then 0<=b<n. X * Also return r = min(n-b, largest power of 2 dividing b) X */ X Xinside_out(n, a, b, r) Xint n, a, *b, *r; X{ X int k, m; X X *r = m = n; X for (*b=0, k=1; k<n; k<<=1) X if (a<<1>=m) { X if (*b==0) *r = k; X *b += k; X a -= m+1>>1; X m >>= 1; X } X else m = m+1>>1; X if (*r>n-*b) *r = n-*b; X} END_OF_FILE if test 1171 -ne `wc -c <'BinRec.c'`; then echo shar: \"'BinRec.c'\" unpacked with wrong size! fi # end of 'BinRec.c' fi if test -f 'CircleRect.c' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'CircleRect.c'\" else echo shar: Extracting \"'CircleRect.c'\" $1513 characters$ sed "s/^X//" >'CircleRect.c' <<'END_OF_FILE' X/* XFast Circle-Rectangle Intersection Checking Xby Clifford A. Shaffer Xfrom "Graphics Gems", Academic Press, 1990 X*/ X X#include "GraphicsGems.h" X Xboolean Check_Intersect(R, C, Rad) X X/* Return TRUE iff rectangle R intersects circle with centerpoint C and X radius Rad. */ X Box2 *R; X Point2 *C; X double Rad; X{ X double Rad2; X X Rad2 = Rad * Rad; X /* Translate coordinates, placing C at the origin. */ X R->max.x -= C->x; R->max.y -= C->y; X R->min.x -= C->x; R->min.y -= C->y; X X if (R->max.x < 0) /* R to left of circle center */ X if (R->max.y < 0) /* R in lower left corner */ X return ((R->max.x * R->max.x + R->max.y * R->max.y) < Rad2); X else if (R->min.y > 0) /* R in upper left corner */ X return ((R->max.x * R->max.x + R->min.y * R->min.y) < Rad2); X else /* R due West of circle */ X return(ABS(R->max.x) < Rad); X else if (R->min.x > 0) /* R to right of circle center */ X if (R->max.y < 0) /* R in lower right corner */ X return ((R->min.x * R->min.x) < Rad2); X else if (R->min.y > 0) /* R in upper right corner */ X return ((R->min.x * R->min.x + R->min.y + R->min.y) < Rad2); X else /* R due East of circle */ X return (R->min.x < Rad); X else /* R on circle vertical centerline */ X if (R->max.y < 0) /* R due South of circle */ X return (ABS(R->max.y) < Rad); X else if (R->min.y > 0) /* R due North of circle */ X return (R->min.y < Rad); X else /* R contains circle centerpoint */ X return(TRUE); X} END_OF_FILE if test 1513 -ne `wc -c <'CircleRect.c'`; then echo shar: \"'CircleRect.c'\" unpacked with wrong size! fi # end of 'CircleRect.c' fi if test -f 'DigitalLine.c' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'DigitalLine.c'\" else echo shar: Extracting \"'DigitalLine.c'\" $943 characters$ sed "s/^X//" >'DigitalLine.c' <<'END_OF_FILE' X/* X * Digital Line Drawing X * by Paul Heckbert X * from "Graphics Gems", Academic Press, 1990 X */ X X/* X * digline: draw digital line from (x1,y1) to (x2,y2), X * calling a user-supplied procedure at each pixel. X * Does no clipping. Uses Bresenham's algorithm. X * X * Paul Heckbert 3 Sep 85 X */ X X#include "GraphicsGems.h" X Xdigline(x1, y1, x2, y2, dotproc) Xint x1, y1, x2, y2; Xvoid (*dotproc)(); X{ X int d, x, y, ax, ay, sx, sy, dx, dy; X X dx = x2-x1; ax = ABS(dx)<<1; sx = SGN(dx); X dy = y2-y1; ay = ABS(dy)<<1; sy = SGN(dy); X X x = x1; X y = y1; X if (ax>ay) { /* x dominant */ X d = ay-(ax>>1); X for (;;) { X (*dotproc)(x, y); X if (x==x2) return; X if (d>=0) { X y += sy; X d -= ax; X } X x += sx; X d += ay; X } X } X else { /* y dominant */ X d = ax-(ay>>1); X for (;;) { X (*dotproc)(x, y); X if (y==y2) return; X if (d>=0) { X x += sx; X d -= ay; X } X y += sy; X d += ax; X } X } X} END_OF_FILE if test 943 -ne `wc -c <'DigitalLine.c'`; then echo shar: \"'DigitalLine.c'\" unpacked with wrong size! fi # end of 'DigitalLine.c' fi if test -f 'FastJitter.c' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'FastJitter.c'\" else echo shar: Extracting \"'FastJitter.c'\" $1720 characters$ sed "s/^X//" >'FastJitter.c' <<'END_OF_FILE' X/* X * Efficient Generation of Sampling Jitter Using Look-up Tables X * by Joseph M. Cychosz X * from "Graphics Gems", Academic Press, 1990 X */ X X/* Jitter.c - Sampling jitter generation routines. X/* X/* Description: X/* Jitter.c contains the routines for generation of sampling X/* jitter using look-up tables. X/* X/* Contents: X/* Jitter1 Generate random jitter function 1. X/* Jitter2 Generate random jitter function 2. X/* JitterInit Initialize look-up tables. X/* */ X X#define NRAN 1024 /* Random number table length */ X Xstatic double URANX[NRAN], /* Random number tables */ X URANY[NRAN]; Xstatic int IRAND[NRAN]; /* Shuffle table */ Xstatic int MASK = NRAN-1; /* Mask for jitter mod function */ Xextern double xranf(); /* Random number generator pro- */ X /* ducing uniform numbers 0 to 1 */ X X/* Jitter1 - Generate random jitter. */ X Xvoid Jitter1 (x,y,s,xj,yj) X int x, y; /* Pixel location */ X int s; /* Sample number for the pixel */ X double *xj, *yj; /* Jitter (x,y) */ X{ X *xj = URANX[ (x + (y<<2) + IRAND[(x+s)&MASK]) & MASK ]; X *yj = URANY[ (y + (x<<2) + IRAND[(y+s)&MASK]) & MASK ]; X} X X X X/* Jitter2 - Generate random jitter. */ X Xvoid Jitter2 (x,y,s,xj,yj) X int x, y; /* Pixel location */ X int s; /* Sample number for the pixel */ X double *xj, *yj; /* Jitter (x,y) */ X{ X *xj = URANX[ ((x | (y<<2)) + IRAND[(x+s)&MASK]) & MASK ]; X *yj = URANY[ ((y | (x<<2)) + IRAND[(y+s)&MASK]) & MASK ]; X} X X X/* JitterInit - Initialize look-up tables. */ X Xvoid JitterInit () X{ X int i; X X for ( i = 0 ; i < NRAN ; i++ ) URANX[i] = xranf(); X for ( i = 0 ; i < NRAN ; i++ ) URANY[i] = xranf(); X for ( i = 0 ; i < NRAN ; i++ ) IRAND[i] = (int) (NRAN * X xranf()); X} END_OF_FILE if test 1720 -ne `wc -c <'FastJitter.c'`; then echo shar: \"'FastJitter.c'\" unpacked with wrong size! fi # end of 'FastJitter.c' fi if test -f 'FixedTrig.c' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'FixedTrig.c'\" else echo shar: Extracting \"'FixedTrig.c'\" $1725 characters$ sed "s/^X//" >'FixedTrig.c' <<'END_OF_FILE' X/* XFixed-Point Trigonometry with CORDIC Iterations Xby Ken Turkowski Xfrom "Graphics Gems", Academic Press, 1990 X*/ X X#define COSCALE 0x22c2dd1c /* 0.271572 */ X#define QUARTER ((int)(3.141592654 / 2.0 * (1 << 28))) Xstatic long arctantab[32] = { /* MS 4 integral bits for radians */ X 297197971, 210828714, 124459457, 65760959, 33381290, 16755422, X 8385879, 4193963, 2097109, 1048571, 524287, 262144, 131072, X 65536, 32768, 16384, 8192, 4096, 2048, 1024, 512, 256, 128, 64, X 32, 16, 8, 4, 2, 1, 0, 0, X}; X XCordicRotate(px, py, theta) Xlong *px, *py; Xregister long theta; /* Assume that abs(theta) <= pi */ X{ X register int i; X register long x = *px, y = *py, xtemp; X register long *arctanptr = arctantab; X X /* The -1 may need to be pulled out and done as a left shift */ X for (i = -1; i <= 28; i++) { X if (theta < 0) { X xtemp = x + (y >> i); X y = y - (x >> i); X x = xtemp; X theta += *arctanptr++; X } else { X xtemp = x - (y >> i); X y = y + (x >> i); X x = xtemp; X theta -= *arctanptr++; X } X } X X *px = frmul(x, COSCALE); /* Compensate for CORDIC enlargement */ X *py = frmul(y, COSCALE); /* frmul(a,b)=(a*b)>>31, high part */ X /* of 64-bit product */ X} X X X X XCordicPolarize(argx, argy) Xlong *argx, *argy; /* We assume these are already in the */ X /* right half plane */ X{ X register long theta, yi, i; X register long x = *argx, y = *argy; X register long *arctanptr = arctantab; X for (i = -1; i <= 28; i++) { X if (y < 0) { /* Rotate positive */ X yi = y + (x >> i); X x = x - (y >> i); X y = yi; X theta -= *arctanptr++; X } else { /* Rotate negative */ X yi = y - (x >> i); X x = x + (y >> i); X y = yi; X theta += *arctanptr++; X } X } X X *argx = frmul(x, COSCALE); X *argy = theta; X} END_OF_FILE if test 1725 -ne `wc -c <'FixedTrig.c'`; then echo shar: \"'FixedTrig.c'\" unpacked with wrong size! fi # end of 'FixedTrig.c' fi if test -f 'HSLtoRGB.c' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'HSLtoRGB.c'\" else echo shar: Extracting \"'HSLtoRGB.c'\" $1736 characters$ sed "s/^X//" >'HSLtoRGB.c' <<'END_OF_FILE' X/* XA Fast HSL-to-RGB Transform Xby Ken Fishkin Xfrom "Graphics Gems", Academic Press, 1990 X*/ X X#include <math.h> X#include <stdio.h> X#include "GraphicsGems.h" X X /* X * RGB-HSL transforms. X * Ken Fishkin, Pixar Inc., January 1989. X */ X X /* X * given r,g,b on [0 ... 1], X * return (h,s,l) on [0 ... 1] X */ Xvoid XRGB_to_HSL (r,g,b,h,s,l) Xdouble r,g,b; Xdouble *h, *s, *l; X{ X double v; X double m; X double vm; X double r2, g2, b2; X X v = MAX(r,g); X v = MAX(v,b); X m = MIN(r,g); X m = MIN(m,b); X X if ((*l = (m + v) / 2.0) <= 0.0) return; X if ((*s = vm = v - m) > 0.0) { X *s /= (*l <= 0.5) ? (v + m ) : X (2.0 - v - m) ; X } else X return; X X X r2 = (v - r) / vm; X g2 = (v - g) / vm; X b2 = (v - b) / vm; X X if (r == v) X *h = (g == m ? 5.0 + b2 : 1.0 - g2); X else if (g == v) X *h = (b == m ? 1.0 + r2 : 3.0 - b2); X else X *h = (r == m ? 3.0 + g2 : 5.0 - r2); X X *h /= 6; X } X X /* X * given h,s,l on [0..1], X * return r,g,b on [0..1] X */ Xvoid XHSL_to_RGB(h,sl,l,r,g,b) Xdouble h,sl,l; Xdouble *r, *g, *b; X{ X double v; X X v = (l <= 0.5) ? (l * (1.0 + sl)) : (l + sl - l * sl); X if (v <= 0) { X *r = *g = *b = 0.0; X } else { X double m; X double sv; X int sextant; X double fract, vsf, mid1, mid2; X X m = l + l - v; X sv = (v - m ) / v; X h *= 6.0; X sextant = h; X fract = h - sextant; X vsf = v * sv * fract; X mid1 = m + vsf; X mid2 = v - vsf; X switch (sextant) { X case 0: *r = v; *g = mid1; *b = m; break; X case 1: *r = mid2; *g = v; *b = m; break; X case 2: *r = m; *g = v; *b = mid1; break; X case 3: *r = m; *g = mid2; *b = v; break; X case 4: *r = mid1; *g = m; *b = v; break; X case 5: *r = v; *g = m; *b = mid2; break; X } X } X} X X END_OF_FILE if test 1736 -ne `wc -c <'HSLtoRGB.c'`; then echo shar: \"'HSLtoRGB.c'\" unpacked with wrong size! fi # end of 'HSLtoRGB.c' fi if test -f 'Hash3D.c' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'Hash3D.c'\" else echo shar: Extracting \"'Hash3D.c'\" $1454 characters$ sed "s/^X//" >'Hash3D.c' <<'END_OF_FILE' X/* XA 3D Grid Hashing Frunction Xby Brian Wyvill Xfrom "Graphics Gems", Academic Press, 1990 X*/ X X/* Test Program for 3D hash function. XIn C the hash function can be defined in a macro which Xavoids a function call Xand the bit operations are defined in the language. X*/ X X#include <stdio.h> X#include <math.h> X#include "GraphicsGems.h" X X#define RANGE 256 X#define NBITS 4 X#define RBITS 4 X#define MASK 0360 X#define HASH(a,b,c) ((((a&MASK)<<NBITS|b&MASK)<<NBITS|c&MASK)>>RBITS) X#define HSIZE 1<<NBITS*3 X#define IABS(x) (int)((x) < 0 ? -(x) : (x)) X Xtypedef struct { X double x,y,z; X} Triple, *RefTriple; X Xtypedef struct { /* linked list of objects to be stored */ X Triple origin; X struct Object *link; X} Object, *RefObject; X Xtypedef struct { /* linked list of voxels (object pointers) */ X RefObject objectList; X struct Voxel *link; X} Voxel, *RefVoxel; X XRefVoxel table[HSIZE]; /* Table of pointers to Voxels */ X X Xcheckrange(z) double z; X{ X if (z < 0 || z >= RANGE) X fprintf(stderr,"%f out of range\n",z), exit(); X} X Xdouble getcoord() X{ X char buf[80]; X double z; X scanf("%s",buf); X z = atof(buf); X checkrange(z); X return z; X} X Xmain() X{ X Triple a; X while (TRUE) { X printf("Enter object position x y z ===> "); X a.x = getcoord(); X a.y = getcoord(); X a.z = getcoord(); X printf("\ncoord: %d %d %d Hashes to %d\n",IABS(a.x),IABS(a.y),IABS(a.z), X HASH(IABS(a.x), IABS(a.y), IABS(a.z) )); X }; X} END_OF_FILE if test 1454 -ne `wc -c <'Hash3D.c'`; then echo shar: \"'Hash3D.c'\" unpacked with wrong size! fi # end of 'Hash3D.c' fi if test -f 'HypotApprox.c' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'HypotApprox.c'\" else echo shar: Extracting \"'HypotApprox.c'\" $1545 characters$ sed "s/^X//" >'HypotApprox.c' <<'END_OF_FILE' X/* XA Fast Approximation to the Hypotenuse Xby Alan Paeth Xfrom "Graphics Gems", Academic Press, 1990 X*/ X Xint idist(x1, y1, x2, y2) X int x1, y1, x2, y2; X { X/* X * gives approximate distance from (x1,y1) to (x2,y2) X * with only overestimations, and then never by more X * than (9/8) + one bit uncertainty. X */ X if ((x2 -= x1) < 0) x2 = -x2; X if ((y2 -= y1) < 0) y2 = -y2; X return (x2 + y2 - (((x2>y2) ? y2 : x2) >> 1) ); X } X Xint PntOnCirc(xp, yp, xc, yc, r) X int xp, yp, xc, yc, r; X { X/* returns true IFF a test point (xp, yp) is to within a X * pixel of the circle of center (xc, yc) and radius r. X * "d" is an approximate length to circle's center, with X * 1.0*r < dist < 1.12*r < (9/8)*r used for coarse testing. X * The 9/8 ratio suggests the code: (x)<<3 and ((x)<<3)-(x). X * Variables xp, yp, r and d should be of 32-bit precision. X * X * Note: (9/8) forms a very tight, proper inner bound but X * must be slackened by one pixel for the outside test (#2) X * to account for the -1/2 pixel absolute error introduced X * when "idist" halves an odd integer; else rough clipping X * will trim occasional points on the circle's perimeter. X */ X int d = idist(xp, yp, xc, yc); X if ( r > d) return(0); /* far-in */ X if (9*r < 8*(d-1)) return(0); /* far-out */ X/* full test: r < hypot(xp-xc,yp-yc) < r+1 */ X xp -= xc; X yp -= yc; X d = xp*xp + yp*yp; X if (d < r*r) return(0); /* near-in */ X r += 1; X if (d > r*r) return(0); /* near-out */ X return(1); /* WITHIN */ X } END_OF_FILE if test 1545 -ne `wc -c <'HypotApprox.c'`; then echo shar: \"'HypotApprox.c'\" unpacked with wrong size! fi # end of 'HypotApprox.c' fi if test -f 'MANIFEST' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'MANIFEST'\" else echo shar: Extracting \"'MANIFEST'\" $4705 characters$ sed "s/^X//" >'MANIFEST' <<'END_OF_FILE' X File Name Archive # Description X----------------------------------------------------------- X 2DClip 1 2D Clipping: A Vector-Based Approach X 2DClip/Makefile 1 Makefile X 2DClip/bio.c 2 Basic operations X 2DClip/box.h 1 BOX definition X 2DClip/clip.c 2 Clipping routines X 2DClip/cross.c 4 Intersection calculation X 2DClip/line.h 1 Major definitions X AALines 1 Rendering Anti-Aliased Lines X AALines/00README 1 Information about AALines Gem X AALines/AALines.c 4 Code to render an anti-aliased line X AALines/AALines.h 1 Symbols & globals X AALines/AAMain.c 1 Calling routine X AALines/AATables.c 4 Initialization of tables and frame buffer X AALines/FastMatMul.c 5 Fast routines to multiply 4x4 matrices X AALines/LongConst.h 1 High-precision constants X AALines/Makefile 1 Makefile X AALines/utah.c 3 Interface to Utah Raster Toolkit X AALines/utah.h 1 Declarations for URT interface X AAPolyScan.c 4 Fast Anti_aliasing Polygon Scan Conversion X Albers.c 3 Albers Equal-Area Conic Map Projection X BinRec.c 1 Recording Animation in Binary Order X BoundSphere.c 3 An Efficient Bounding Sphere X BoxSphere.c 2 Box-Sphere Intersection Checking X CircleRect.c 1 Fast Circle-Rectangle Intersection Checking X ConcaveScan.c 4 Concave Polygon Scan Conversion X DigitalLine.c 1 Digital Line Drawing X Dissolve.c 3 A Digital "Dissolve" Effect X DoubleLine.c 3 Symmetric Double Step Line Algorithm X FastJitter.c 1 Efficient Generation of Sampling Jitter X FitCurves.c 5 Automatically Fit Digitized Curves X FixedTrig.c 1 Fixed-Point Trig with CORDIC Iterations X Forms.c 4 Forms, Vectors, and Transformations X GGVecLib.c 5 2D and 3D Vector C Library X GraphicsGems.h 3 Graphics Gems header file X HSLtoRGB.c 1 A Fast HSL-to-RGB Transform X Hash3D.c 1 3D Grid Hashing Function X HypotApprox.c 1 A Fast Approximation to the Hypotenuse X Interleave.c 4 Bit Interleaving for Quad- or Octrees X Label.c 2 Nice Numbers for Graph Labels X LineEdge.c 3 Fast Line-Edge Intersections on a Uniform Grid X MANIFEST 1 This shipping list X Makefile 2 Makefile for the whole shebang X MatrixInvert.c 3 Matrix Inversion X MatrixOrtho.c 1 Matrix Orthogonalization X MatrixPost.c 2 Efficient Post-Concatenation of Trans. Matrices X Median.c 2 Median Finding on a 3x3 Grid X NearestPoint.c 5 Nearest-Point-On-Curve and Bezier Root-Finder X OrderDither.c 2 Ordered Dithering X PixelInteger.c 1 Proper Treatment of Pixels As Integers X PntOnLine.c 2 A Fast 2D Point-On-Line Test X PolyScan 1 Convex Polygon Scan Conversion & Clipping X PolyScan/Makefile 1 Makefile X PolyScan/fancytest.c 2 Phong-shading a Texture mapping test X PolyScan/poly.c 2 Simple utilities for polygon data structure X PolyScan/poly.h 2 Definitions for polygon package X PolyScan/poly_clip.c 3 Homogeneous 3D polygon clipper X PolyScan/poly_scan.c 3 Convex polygon point-sampled scan conversion X PolyScan/scantest.c 2 Gouraud shading and Z-buffer demo X Quaternions.c 2 Using Quaternions for Coding 3D Transformations X README 1 General information X RGBTo4Bits.c 1 Mapping RGB Triples Onto Four Bits X RayBox.c 1 Fast Ray-Box Intersection X RayPolygon.c 1 An Efficient Ray-Polygon Intersection X Roots3And4.c 3 Cubic and Quartic Roots X SeedFill.c 2 A Seed Fill Algorithm X SquareRoot.c 2 A High-Speed, Low-Precision Square Root X Sturm 1 Using Sturm Sequences to Bracket Real Roots X Sturm/Makefile 1 Makefile X Sturm/main.c 2 Sample driver program X Sturm/solve.h 1 Useful constants and types X Sturm/sturm.c 4 Functions to build and evaluate Sturm sequence X Sturm/util.c 1 Root polishing and evaluating utilities X TransBox.c 1 Transforming Axis-Aligned Bounding Boxes X TriPoints.c 2 Generating Random Points in Triangles X ViewTrans.c 1 3D Viewing and Rotation using Orthonormal Bases END_OF_FILE if test 4705 -ne `wc -c <'MANIFEST'`; then echo shar: \"'MANIFEST'\" unpacked with wrong size! fi # end of 'MANIFEST' fi if test -f 'MatrixOrtho.c' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'MatrixOrtho.c'\" else echo shar: Extracting \"'MatrixOrtho.c'\" $1335 characters$ sed "s/^X//" >'MatrixOrtho.c' <<'END_OF_FILE' X/* XMatrix Orthogonalization XEric Raible Xfrom "Graphics Gems", Academic Press, 1990 X*/ X X/* X * Reorthogonalize matrix R - that is find an orthogonal matrix that is X * "close" to R by computing an approximation to the orthogonal matrix X * X * T -1/2 X * RC = R(R R) X * T -1 X * [RC is orthogonal because (RC) = (RC) ] X * -1/2 X * To compute C, we evaluate the Taylor expansion of F(x) = (I + x) X * (where x = C - I) about x=0. X * This gives C = I - (1/2)x + (3/8)x^2 - (5/16)x^3 + ... X */ X X#include "GraphicsGems.h" X Xstatic float coef[10] = /* From mathematica */ X { 1, -1/2., 3/8., -5/16., 35/128., -63/256., X 231/1024., -429/2048., 6435/32768., -12155/65536. }; X XMATRIX_reorthogonalize (R, limit) X Matrix R; X{ X Matrix I, Temp, X, X_power, Sum; X int power; X X limit = MAX(limit, 10); X X MATRIX_transpose (R, Temp); /* Rt */ X MATRIX_multiply (Temp, R, Temp); /* RtR */ X MATRIX_identify (I); X MATRIX_subtract (Temp, I, X); /* RtR - I */ X MATRIX_identify (X_power); /* X^0 */ X MATRIX_identify (Sum); /* coef[0] * X^0 */ X X for (power = 1; power < limit; ++power) X { X MATRIX_multiply (X_power, X, X_power); X MATRIX_constant_multiply (coef[power], X_power, Temp); X MATRIX_add (Sum, Temp, Sum); X } X X MATRIX_multiply (R, Sum, R); X} END_OF_FILE if test 1335 -ne `wc -c <'MatrixOrtho.c'`; then echo shar: \"'MatrixOrtho.c'\" unpacked with wrong size! fi # end of 'MatrixOrtho.c' fi if test -f 'PixelInteger.c' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'PixelInteger.c'\" else echo shar: Extracting \"'PixelInteger.c'\" $1534 characters$ sed "s/^X//" >'PixelInteger.c' <<'END_OF_FILE' X/* XProper Treatment of Pixels as Integers Xby Alan Paeth Xfrom "Graphics Gems", Academic Press, 1990 X*/ X X#define Min code[2] X#define Med code[1] X#define Max code[0] X#define NCODE 3 X X/* X * A call to getplanes of the form: X * getplanes(&red, &green, &blue, 256, "grb"); X * X * fills the first three integer pointers with (near) identical X * values which maximize red*green*blue <= 256. The final parameter X * string defines tie-break order, here green>=red>=blue (the usual X * default). The present code procedure calls "err(string, arg)" X * given bad parameters; it is a simple task to rewrite the code as X * a function which returns a success/failure code(s), as needed. X * X * In the example given above the code fills in the values X * red = 6, green = 7, blue = 6. X */ X Xgetplanes(r, g, b, n, bias) X int *r, *g, *b; X char *bias; X { X int i, code[NCODE]; X if(strlen(bias) != NCODE ) X err("bias string \"%s\" wrong length",bias); X Min = Med = Max = 0; X *r = *g = *b = 0; X while(Min*Min*Min <= n) Min++; X Min--; X while(Med*Med*Min <= n) Med++; X Med--; X Max = n/(Min*Med); X for( i = 0; i < NCODE; i++ ) X { X switch(bias[i]) X { X case 'r': case 'R': *r = code[i]; break; X case 'g': case 'G': *g = code[i]; break; X case 'b': case 'B': *b = code[i]; break; X default: err("bad bias character: \'%c\'",bias[i]); break; X } X } X if (!(*r && *g && *b)) err("bias string \"%s\" deficient", bias); X } X END_OF_FILE if test 1534 -ne `wc -c <'PixelInteger.c'`; then echo shar: \"'PixelInteger.c'\" unpacked with wrong size! fi # end of 'PixelInteger.c' fi if test ! -d 'PolyScan' ; then echo shar: Creating directory \"'PolyScan'\" mkdir 'PolyScan' fi if test -f 'PolyScan/Makefile' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'PolyScan/Makefile'\" else echo shar: Extracting \"'PolyScan/Makefile'\" $380 characters$ sed "s/^X//" >'PolyScan/Makefile' <<'END_OF_FILE' X# Makefile for scantest, test program for generic convex polygon scan conversion X# X# Note: fancytest.c needs a main routine and several auxiliary routines X# in order to be compiled. X XCFLAGS = $(GENCFLAGS) X Xscantest: scantest.o poly_scan.o poly.o X $(CC) $(CFLAGS) -o scantest scantest.o poly_scan.o poly.o -lm X Xclean: X /bin/rm -f scantest.o poly_clip.o poly_scan.o poly.o scantest END_OF_FILE if test 380 -ne `wc -c <'PolyScan/Makefile'`; then echo shar: \"'PolyScan/Makefile'\" unpacked with wrong size! fi # end of 'PolyScan/Makefile' fi if test -f 'README' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'README'\" else echo shar: Extracting \"'README'\" $5838 characters$ sed "s/^X//" >'README' <<'END_OF_FILE' X[ This package last updated Fri Oct 12 15:53:09 EDT 1990. ] X XREADME X XThis package contains the most up-to-date versions of the C source Xfiles from the book "Graphics Gems" (Editor Andrew S. Glassner, XAcademic Press, 1990 ISBM 0-12-286165-5, 833 pgs.). X XAll known bugs have been fixed, formatting problems have been Xcorrected, and enchancements to some of the original Gems have Xbeen made. X XMakefiles are provided that create stand-alone programs, many object Xfiles, and "gemlib.a". This Graphics Gem Library is created for Xcompilation-testing only, and is not intended to be a usable library X(although it may become so in the future). Indeed, many of the Gems Xwill not compile or run properly without the addition of functions, Xtables, and the like. See the book and the Makefile for more details. X XEach Gem is made available on an as-is basis; although Xconsiderable effort has been expended to check the programs Xas originally designed and their release in electronic form, Xthe authors and the publisher make no guarantees or Xwarrantees about the correctness of any of these programs or Xalgorithms. X XThe authors and the publisher hold no copyright restrictions Xon any of these files; this source code is public domain, and Xis freely available to the entire computer graphics community Xfor study, use, and modification. We do request that the Xcomment at the top of each file, identifying the original Xauthor and its original publication in the book Graphics XGems, be retained in all programs that use these files. X XAn archive of the most current versions of all the Gems is maintained Xon weedeater.math.yale.edu (130.132.23.17) and is available via Xanonymous ftp in pub/GraphicsGems/src. X XYou are encouraged to submit bug fixes, skeleton programs, and the like Xto Craig Kolb (kolb@yale.edu). X XAndrew Glassner / Craig Kolb X X================ X XThe table below gives the correspondence between each source Xfile in this directory and the name of the Gem it implements. XEach implementation illustrates one way to realize the Xtechniques described by the accompanying Gem in the book. XThe files here contain only the source code for that Xrealization. For a more complete description of the Xalgorithms and their applications see the Gems of the same Xname in the first 11 Chapters of the book. X X---------- header files ---------- XGraphicsGems.h / Graphics Gems C Header File X X---------- C code ---------- X2DClip/* / Two-Dimensional Clipping: X A Vector-Based Approach XAALines/* / Rendering Anti-Aliased Lines XAAPolyScan.c / Fast Anti-Aliasing Polygon X Scan Conversion XAlbers.c / Albers Equal-Area Conic Map X Projection XBinRec.c / Recording Animation in Binary Order X For Progressive Temporal Refinement XBoundSphere.c / An Efficient Bounding Sphere XBoxSphere.c / A Simple Method for Box-Sphere X Intersection Checking XCircleRect.c / Fast Circle-Rectangle Intersection X Checking XConcaveScan.c / Concave Polygon Scan Conversion XDigitalLine.c / Digital Line Drawing XDissolve.c / A Digital "Dissolve" Effect XDoubleLine.c / Symmetric Double Step Line Algorithm XFastJitter.c / Efficient Generation of Sampling X Jitter Using Look-up Tables XFitCurves.c / An Algorithm for Automatically X Fitting Digitized Curves XFixedTrig.c / Fixed-Point Trigonometry with X CORDIC Iterations XForms.c / Forms, Vectors, and Transforms XGGVecLib.c / 2D And 3D Vector C Library XHSLtoRGB.c / A Fast HSL-to-RGB Transform XHash3D.c / 3D Grid Hashing Function XHypotApprox.c / A Fast Approximation to X the Hypotenuse XInterleave.c / Bit Interleaving for Quad- X or Octrees XLabel.c / Nice Numbers for Graph Labels XLineEdge.c / Fast Line-Edge Intersections On X A Uniform Grid XMatrixInvert.c / Matrix Inversion XMatrixOrtho.c / Matrix Orthogonalization XMatrixPost.c / Efficient Post-Concatenation of X Transformation Matrices XMedian.c / Median Finding on a 3x3 Grid XNearestPoint.c / Solving the X Nearest-Point-On-Curve Problem X and X A Bezier Curve-Based Root-Finder XOrderDither.c / Ordered Dithering XPixelInteger.c / Proper Treatment of Pixels X As Integers XPntOnLine.c / A Fast 2D Point-On-Line Test XPolyScan/* / Generic Convex Polygon X Scan Conversion and Clipping XQuaternions.c / Using Quaternions for Coding X 3D Transformations XRGBTo4Bits.c / Mapping RGB Triples Onto Four Bits XRayBox.c / Fast Ray-Box Intersection XRayPolygon.c / An Efficient Ray-Polygon X Intersection XRoots3And4.c / Cubic and Quartic Roots XSeedFill.c / A Seed Fill Algorithm XSquareRoot.c / A High-Speed, Low-Precision X Square Root XSturm/* / Using Sturm Sequences to Bracket X Real Roots of Polynomial Equations XTransBox.c / Transforming Axis-Aligned X Bounding Boxes XTriPoints.c / Generating Random Points X In Triangles XViewTrans.c / 3D Viewing and Rotation Using X Orthonormal Bases END_OF_FILE if test 5838 -ne `wc -c <'README'`; then echo shar: \"'README'\" unpacked with wrong size! fi # end of 'README' fi if test -f 'RGBTo4Bits.c' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'RGBTo4Bits.c'\" else echo shar: Extracting \"'RGBTo4Bits.c'\" $1448 characters$ sed "s/^X//" >'RGBTo4Bits.c' <<'END_OF_FILE' X/* XMapping RGB Triples onto Four Bits Xby Alan Paeth Xfrom "Graphics Gems", Academic Press, 1990 X*/ X Xremap8(R, G, B, R2, G2, B2) X float R, G, B, *R2, *G2, *B2; X { X/* X * remap8 maps floating (R,G,B) triples onto quantized X * (R2,B2,B2) triples and returns the code (vertex) X * value/color table entry for the quantization. The X * points (eight) are the vertices of the cube. X */ X int code; X *R2 = *G2 = *B2 = 0.0; X code = 0; X if (R >= 0.5) { *R2 = 1.0; code |= 1; } X if (G >= 0.5) { *G2 = 1.0; code |= 2; } X if (B >= 0.5) { *B2 = 1.0; code |= 4; } X return(code); X } X X/* X * remap14 maps floating (R,G,B) triples onto quantized X * (R2,B2,B2) triples and returns the code (vertex) X * value/color table entry for the quantization. The X * points (fourteen) are the vertices of the cuboctahedron. X */ X Xfloat rval[] = { 0.,.5 ,.5 , 1.,.0 , 0., 0.,.5, X .5 , 1., 1., 1., 0.,.5 ,.5 , 1.}; Xfloat gval[] = { 0.,.5 , 0., 0.,.5 , 1., 0.,.5, X .5 , 1., 0.,.5 , 1., 1.,.5 , 1.}; Xfloat bval[] = { 0., 0.,.5 , 0.,.5 , 0., 1.,.5, X .5 , 0., 1.,.5 , 1.,.5 , 1., 1.}; X Xint remap14(R, G, B, R2, G2, B2) X float R, G, B, *R2, *G2, *B2; X { X int code = 0; X if ( R + G + B > 1.5) code |= 8; X if (-R + G + B > 0.5) code |= 4; X if ( R - G + B > 0.5) code |= 2; X if ( R + G - B > 0.5) code |= 1; X *R2 = rval[code]; X *G2 = gval[code]; X *B2 = bval[code]; X return(code); X } END_OF_FILE if test 1448 -ne `wc -c <'RGBTo4Bits.c'`; then echo shar: \"'RGBTo4Bits.c'\" unpacked with wrong size! fi # end of 'RGBTo4Bits.c' fi if test -f 'RayBox.c' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'RayBox.c'\" else echo shar: Extracting \"'RayBox.c'\" $1793 characters$ sed "s/^X//" >'RayBox.c' <<'END_OF_FILE' X/* XFast Ray-Box Intersection Xby Andrew Woo Xfrom "Graphics Gems", Academic Press, 1990 X*/ X X#include "GraphicsGems.h" X X#define NUMDIM 3 X#define RIGHT 0 X#define LEFT 1 X#define MIDDLE 2 X Xchar HitBoundingBox(minB,maxB, origin, dir,coord) Xdouble minB[NUMDIM], maxB[NUMDIM]; /*box */ Xdouble origin[NUMDIM], dir[NUMDIM]; /*ray */ Xdouble coord[NUMDIM]; /* hit point */ X{ X char inside = TRUE; X char quadrant[NUMDIM]; X register int i; X int whichPlane; X double maxT[NUMDIM]; X double candidatePlane[NUMDIM]; X X /* Find candidate planes; this loop can be avoided if X rays cast all from the eye(assume perpsective view) */ X for (i=0; i<NUMDIM; i++) X if(origin[i] < minB[i]) { X quadrant[i] = LEFT; X candidatePlane[i] = minB[i]; X inside = FALSE; X }else if (origin[i] > maxB[i]) { X quadrant[i] = RIGHT; X candidatePlane[i] = maxB[i]; X inside = FALSE; X }else { X quadrant[i] = MIDDLE; X } X X /* Ray origin inside bounding box */ X if(inside) { X coord = origin; X return (TRUE); X } X X X /* Calculate T distances to candidate planes */ X for (i = 0; i < NUMDIM; i++) X if (quadrant[i] != MIDDLE && dir[i] !=0.) X maxT[i] = (candidatePlane[i]-origin[i]) / dir[i]; X else X maxT[i] = -1.; X X /* Get largest of the maxT's for final choice of intersection */ X whichPlane = 0; X for (i = 1; i < NUMDIM; i++) X if (maxT[whichPlane] < maxT[i]) X whichPlane = i; X X /* Check final candidate actually inside box */ X if (maxT[whichPlane] < 0.) return (FALSE); X for (i = 0; i < NUMDIM; i++) X if (whichPlane != i) { X coord[i] = origin[i] + maxT[whichPlane] *dir[i]; X if ((quadrant[i] == RIGHT && coord[i] < minB[i]) || X (quadrant[i] == LEFT && coord[i] > maxB[i])) X return (FALSE); /* outside box */ X }else { X coord[i] = candidatePlane[i]; X } X return (TRUE); /* ray hits box */ X} X END_OF_FILE if test 1793 -ne `wc -c <'RayBox.c'`; then echo shar: \"'RayBox.c'\" unpacked with wrong size! fi # end of 'RayBox.c' fi if test -f 'RayPolygon.c' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'RayPolygon.c'\" else echo shar: Extracting \"'RayPolygon.c'\" $1553 characters$ sed "s/^X//" >'RayPolygon.c' <<'END_OF_FILE' X/* XAn Efficient Ray/Polygon Intersection Xby Didier Badouel Xfrom "Graphics Gems", Academic Press, 1990 X*/ X X/* the value of t is computed. X * i1 and i2 come from the polygon description. X * V is the vertex table for the polygon and N the X * associated normal vectors. X */ XP[0] = ray.O[0] + ray.D[0]*t; XP[1] = ray.O[1] + ray.D[1]*t; XP[2] = ray.O[2] + ray.D[2]*t; Xu0 = P[i1] - V[0][i1]; v0 = P[i2] - V[0][i2]; Xinter = FALSE; i = 2; Xdo { X /* The polygon is viewed as (n-2) triangles. */ X u1 = V[i-1][i1] - V[0][i1]; v1 = V[i-1][i2] - V[0][i2]; X u2 = V[i ][i1] - V[0][i1]; v2 = V[i ][i2] - V[0][i2]; X X if (u1 == 0) { X beta = u0/u2; X if ((beta >= 0.)&&(beta <= 1.)) { X alpha = (v0 - beta*v2)/v1; X inter = ((alpha >= 0.)&&(alpha+beta) <= 1.)); X } X } else { X beta = (v0*u1 - u0*v1)/(v2*u1 - u2*v1); X if ((beta >= 0.)&&(beta <= 1.)) { X alpha = (u0 - beta*u2)/u1; X inter = ((alpha >= 0)&&((alpha+beta) <= 1.)); X } X } X} while ((!inter)&&(++i < poly.n)); X Xif (inter) { X /* Storing the intersection point. */ X ray.P[0] = P[0]; ray.P[1] = P[1]; ray.P[2] = P[2]; X /* the normal vector can be interpolated now or later. */ X if (poly.interpolate) { X gamma = 1 - (alpha+beta); X ray.normal[0] = gamma * N[0][0] + alpha * N[i-1][0] + X beta * N[i][0]; X ray.normal[1] = gamma * N[0][1] + alpha * N[i-1][1] + X beta * N[i][1]; X ray.normal[2] = gamma * N[0][2] + alpha * N[i-1][2] + X beta * N[i][2]; X } X} Xreturn (inter); END_OF_FILE if test 1553 -ne `wc -c <'RayPolygon.c'`; then echo shar: \"'RayPolygon.c'\" unpacked with wrong size! fi # end of 'RayPolygon.c' fi if test ! -d 'Sturm' ; then echo shar: Creating directory \"'Sturm'\" mkdir 'Sturm' fi if test -f 'Sturm/Makefile' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'Sturm/Makefile'\" else echo shar: Extracting \"'Sturm/Makefile'\" $211 characters$ sed "s/^X//" >'Sturm/Makefile' <<'END_OF_FILE' X# X# Makefile X# X# command file for make to compile the solver. X Xsolve: main.o sturm.o util.o X cc -o solve main.o sturm.o util.o -lm X Xclean: X /bin/rm -f main.o sturm.o util.o solve X Xmain.o sturm.o util.o: solve.h END_OF_FILE if test 211 -ne `wc -c <'Sturm/Makefile'`; then echo shar: \"'Sturm/Makefile'\" unpacked with wrong size! fi # end of 'Sturm/Makefile' fi if test -f 'Sturm/solve.h' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'Sturm/solve.h'\" else echo shar: Extracting \"'Sturm/solve.h'\" $710 characters$ sed "s/^X//" >'Sturm/solve.h' <<'END_OF_FILE' X X/* X * solve.h X * X * some useful constants and types. X */ X#define MAX_ORDER 12 X/* maximum order for a polynomial */ X X#define RELERROR 1.0e-14 X/* smallest relative error we want */ X X#define MAXPOW 32 X/* max power of 10 we wish to search to */ X X#define MAXIT 800 X/* max number of iterations */ X X/* a coefficient smaller than SMALL_ENOUGH is considered to X be zero (0.0). */ X X#define SMALL_ENOUGH 1.0e-12 X X X/* X * structure type for representing a polynomial X */ Xtypedef struct p { X int ord; X double coef[MAX_ORDER]; X} poly; X Xextern int modrf(); Xextern int numroots(); Xextern int numchanges(); Xextern int buildsturm(); X Xextern double evalpoly(); X X END_OF_FILE if test 710 -ne `wc -c <'Sturm/solve.h'`; then echo shar: \"'Sturm/solve.h'\" unpacked with wrong size! fi # end of 'Sturm/solve.h' fi if test -f 'Sturm/util.c' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'Sturm/util.c'\" else echo shar: Extracting \"'Sturm/util.c'\" $1768 characters$ sed "s/^X//" >'Sturm/util.c' <<'END_OF_FILE' X X/* X * util.c X * X * some utlity functions for root polishing and evaluating X * polynomials. X */ X#include <math.h> X#include <stdio.h> X#include "solve.h" X X/* X * evalpoly X * X * evaluate polynomial defined in coef returning its value. X */ Xdouble Xevalpoly (ord, coef, x) X int ord; X double *coef, x; X{ X double *fp, f; X X fp = &coef[ord]; X f = *fp; X X for (fp--; fp >= coef; fp--) X f = x * f + *fp; X X return(f); X} X X X/* X * modrf X * X * uses the modified regula-falsi method to evaluate the root X * in interval [a,b] of the polynomial described in coef. The X * root is returned is returned in *val. The routine returns zero X * if it can't converge. X */ Xint Xmodrf(ord, coef, a, b, val) X int ord; X double *coef; X double a, b, *val; X{ X int its; X double fa, fb, x, lx, fx, lfx; X double *fp, *scoef, *ecoef; X X scoef = coef; X ecoef = &coef[ord]; X X fb = fa = *ecoef; X for (fp = ecoef - 1; fp >= scoef; fp--) { X fa = a * fa + *fp; X fb = b * fb + *fp; X } X X /* X * if there is no sign difference the method won't work X */ X if (fa * fb > 0.0) X return(0); X X if (fabs(fa) < RELERROR) { X *val = a; X return(1); X } X X if (fabs(fb) < RELERROR) { X *val = b; X return(1); X } X X lfx = fa; X lx = a; X X X for (its = 0; its < MAXIT; its++) { X X x = (fb * a - fa * b) / (fb - fa); X X fx = *ecoef; X for (fp = ecoef - 1; fp >= scoef; fp--) X fx = x * fx + *fp; X X if (fabs(x) > RELERROR) { X if (fabs(fx / x) < RELERROR) { X *val = x; X return(1); X } X } else if (fabs(fx) < RELERROR) { X *val = x; X return(1); X } X X if ((fa * fx) < 0) { X b = x; X fb = fx; X if ((lfx * fx) > 0) X fa /= 2; X } else { X a = x; X fa = fx; X if ((lfx * fx) > 0) X fb /= 2; X } X X lx = x; X lfx = fx; X } X X fprintf(stderr, "modrf overflow %f %f %f\n", a, b, fx); X X return(0); X} X X X END_OF_FILE if test 1768 -ne `wc -c <'Sturm/util.c'`; then echo shar: \"'Sturm/util.c'\" unpacked with wrong size! fi # end of 'Sturm/util.c' fi if test -f 'TransBox.c' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'TransBox.c'\" else echo shar: Extracting \"'TransBox.c'\" $1672 characters$ sed "s/^X//" >'TransBox.c' <<'END_OF_FILE' X/* XTransforming Axis-Aligned Bounding Boxes Xby Jim Arvo Xfrom "Graphics Gems", Academic Press, 1990 X*/ X X#include "GraphicsGems.h" X/* Transforms a 3D axis-aligned box via a 3x3 matrix and a translation X * vector and returns an axis-aligned box enclosing the result. */ X Xvoid Transform_Box( M, T, A, B ) XMatrix3 M; /* Transform matrix. */ XVector3 T; /* Translation matrix. */ XBox3 A; /* The original bounding box. */ XBox3 *B; /* The transformed bounding box. */ X { X float a, b; X float Amin[3], Amax[3]; X float Bmin[3], Bmax[3]; X int i, j; X X /*Copy box A into a min array and a max array for easy reference.*/ X X Amin[0] = A.min.x; Amax[0] = A.max.x; X Amin[1] = A.min.y; Amax[1] = A.max.y; X Amin[2] = A.min.z; Amax[2] = A.max.z; X X /* Take care of translation by beginning at T. */ X X Bmin[0] = Bmax[0] = T.x; X Bmin[1] = Bmax[1] = T.y; X Bmin[2] = Bmax[2] = T.z; X X /* Now find the extreme points by considering the product of the */ X /* min and max with each component of M. */ X X for( i = 0; i < 3; i++ ) X for( j = 0; j < 3; j++ ) X { X a = M.element[i][j] * Amin[j]; X b = M.element[i][j] * Amax[j]; X if( a < b ) X X { X Bmin[i] += a; X Bmax[i] += b; X } X else X { X Bmin[i] += b; X Bmax[i] += a; X } X } X X /* Copy the result into the new box. */ X X B->min.x = Bmin[0]; B->max.x = Bmax[0]; X B->min.y = Bmin[1]; B->max.y = Bmax[1]; X B->min.z = Bmin[2]; B->max.z = Bmax[2]; X X } END_OF_FILE if test 1672 -ne `wc -c <'TransBox.c'`; then echo shar: \"'TransBox.c'\" unpacked with wrong size! fi # end of 'TransBox.c' fi if test -f 'ViewTrans.c' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'ViewTrans.c'\" else echo shar: Extracting \"'ViewTrans.c'\" $1575 characters$ sed "s/^X//" >'ViewTrans.c' <<'END_OF_FILE' X/* X3D Viewing and Rotation Using Orthonormal Bases Xby Steve Cunningham Xfrom "Grahics Gems", Academic Press, 1990 X*/ X X/* X * Transformations are presented as 4 by 3 matrices, omitting the X * fourth column to save memory. X * X * Functions are used from the Graphics Gems vector C library X */ X X X#include "GraphicsGems.h" X Xtypedef float Transform[4][3]; X Xvoid BuildViewTransform( VRP, EP, UP, T ) X Point3 VRP, EP, UP; X Transform T; X{ X Vector3 U, V, N; X float dot; X X /* X * Compute vector N = EP - VRP and normalize N X */ X N.x = EP.x - VRP.x; N.y = EP.y - VRP.y; N.z = EP.z - VRP.z; X V3Normalize(&N); X X /* X * Compute vector V = UP - VRP X * Make vector V orthogonal to N and normalize V X */ X V.x = UP.x - VRP.x; V.y = UP.y - VRP.y; V.z = UP.z - VRP.z; X dot = V3Dot(&V,&N); X V.x -= dot * N.x; V.y -= dot * N.y; V.z -= dot * N.z; X V3Normalize(&V); X X X /* X * Compute vector U = V x N (cross product) X */ X V3Cross(&V,&N,&U); X X /* X * Write the vectors U, V, and N as the first three rows of the X * first, second, and third columns of T, respectively X */ X T[0][0] = U.x; /* column 1 , vector U */ X T[1][0] = U.y; X T[2][0] = U.z; X T[0][1] = V.x; /* column 2 , vector V */ X T[1][1] = V.y; X T[2][1] = V.z; X T[0][2] = N.x; /* column 3 , vector N */ X T[1][2] = N.y; X T[2][2] = N.z; X X /* X * Compute the fourth row of T to include the translation of X * VRP to the origin X */ X T[3][0] = - U.x * VRP.x - U.y * VRP.y - U.z * VRP.z; X T[3][1] = - V.x * VRP.x - V.y * VRP.y - V.z * VRP.z; X T[3][2] = - N.x * VRP.x - N.y * VRP.y - N.z * VRP.z; X X return; X} X X END_OF_FILE if test 1575 -ne `wc -c <'ViewTrans.c'`; then echo shar: \"'ViewTrans.c'\" unpacked with wrong size! fi # end of 'ViewTrans.c' fi echo shar: End of archive 1 $of 5$. cp /dev/null ark1isdone MISSING="" for I in 1 2 3 4 5 ; do if test ! -f ark${I}isdone ; then MISSING="${MISSING} ${I}" fi done if test "${MISSING}" = "" ; then echo You have unpacked all 5 archives. rm -f ark[1-9]isdone else echo You still need to unpack the following archives: echo " " ${MISSING} fi ## End of shell archive. exit 0